class Solution
{
public:
    long long numberOfPairs(vector<int> &nums1, vector<int> &nums2, int k)
    {
        long long result = 0;

        unordered_map<int, int> nums1Count;
        for (int num : nums1)
        {
            if (num % k == 0)
            {
                ++nums1Count[num / k];
            }
        }

        unordered_map<int, int> nums2Count;
        for (int num : nums2)
        {
            ++nums2Count[num];
        }

        for (auto &[num1, count1] : nums1Count)
        {
            for (int i = 1; i <= sqrt(num1); ++i)
            {
                if (num1 % i == 0)
                {
                    if (nums2Count.count(i))
                    {
                        result += (long long)count1 * nums2Count[i];
                    }
                    int j = num1 / i;
                    if (i != j && nums2Count.count(j))
                    {
                        result += (long long)count1 * nums2Count[j];
                    }
                }
            }
        }
        return result;
    }
};